###############################################################################
# cantor.py v. 0.6
# (c) 2008, Gabriel F. Pickard
#
# Performs a special variant of Cantor coding, where (hyper)square
# is recursively separated into (hyperquadrants) for encoding.
#
# See http://gpickard.wordpress.com for more details
#
# python cantor.py 010203305631
# python cantor.py -a A,B,C,D -v ABBA
# python cantor.py -r reversed
#
###############################################################################
#
#    This program is free software; you can redistribute it and/or modify
#    it under the terms of the GNU General Public License as published by
#    the Free Software Foundation; either version 2 of the License, or
#    (at your option) any later version.
#
#    This program is distributed in the hope that it will be useful,
#    but WITHOUT ANY WARRANTY; without even the implied warranty of
#    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
#    GNU General Public License for more details.
#
#    You should have received a copy of the GNU General Public License
#    along with this program; if not, write to the Free Software
#    Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA  02110-1301 USA
#
###############################################################################

from optparse import OptionParser
from copy import copy
import math

def scalar_prod(scalar, vector):
    result = copy(vector)
    for i in range(len(vector)):
        result[i] *= scalar
    return result

def lin_combine(v1, v2):
    result = copy(v1)
    for i in range(len(v1)):
        result[i] += v2[i]
    return result


MID = 0.0
OFFSET = 0.5
DEFAULT = 0.5

def calc_directions(alphabet, dim, offset = OFFSET, default = DEFAULT, mid = MID, prefix = []):
    """Provides list of directional vectors for every symbol in the alphabet."""
    if len(alphabet) < 2:
        return [prefix + [mid+offset] * (len(alphabet) - 1) + [mid+default] * (dim - len(alphabet) + 1)]

    else:
        la = len(alphabet)/2
        d1 = calc_directions(alphabet[:la], dim -1, offset, default, mid, prefix + [mid+offset])
        d2 = calc_directions(alphabet[la:], dim -1, offset, default, mid, prefix + [mid-offset])

        return d1 + d2


def calc_dim(alphabet):
    dim = 1
    d = 2
    while d < len(alphabet):
        d *= 2
        dim += 1

    return dim

def setup_directions(alphabet, offset = OFFSET, default = DEFAULT, mid = MID):
    dim = calc_dim(alphabet)
    return (calc_directions(alphabet, dim, offset, default, mid), dim)

def cantor_coding(sequence, alphabet = None, directions = None,\
                  reverse = True, calc_directions = calc_directions,\
                  verbose = False, dim = None):
    """Computes Cantor coding for given sequence.

       Defaults to reverse mode, where last symbol is easiest to decode."""

    if alphabet is None and directions is None:
        alphabet = list(set(sequence))
    elif alphabet is None:
        alphabet = range(len(directions))
    if dim is None:
        dim = calc_dim(alphabet)

    if directions is None:
        directions = calc_directions(alphabet, dim)
    cantor_code = [MID for x in xrange(dim)]

    if verbose:
        j = 0
    scale = 1.0
    for s in sequence:
        i = alphabet.index(s)
        offset = directions[i]
        if not reverse:
            offset = scalar_prod(scale,  offset)
        else:
            cantor_code = scalar_prod(0.5, cantor_code)
        cantor_code = lin_combine(cantor_code, offset)

        if verbose:
            print ".............................."
            print "index:  " + str(j)
            print "symbol: " + s
            print "offset: " + str(offset)
            print "code:   "+ str(cantor_code)
            j += 1

        scale *= 0.5

    return (cantor_code, alphabet, directions)


def main():
    parser = OptionParser("usage: %prog [options] string")
    parser.add_option("-a", "--alphabet", dest="alphabet",
                      help="Use given alphabet.")
    parser.add_option("-r", "--reverse",
                      action="store_true", dest="reverse", default=False,
                      help="Perform reverse encoding. So that last (not first) symbol is easiest accessible.\n")
    parser.add_option("-v", "--verbose",
                      action="store_true", dest="verbose", default=False,
                      help="Print status messages to stdout.\nPrints encoding and offset for every step.")

    (options, args) = parser.parse_args()
    VERBOSE = options.verbose

    if len(args) > 0:
        alphabet = options.alphabet
        if not alphabet is None:
            alphabet = [a.strip() for a in options.alphabet.split(',')]

        if VERBOSE:
            print "..........................................."
            print "Calculating:"

        (code, alphabet, dirs) = cantor_coding(args[0], alphabet,\
                    reverse = options.reverse, verbose = options.verbose)

        print "..........................................."
        print "Directions assigned to symbols in alphabet:"
        for a in xrange(len(alphabet)):
            print "\t" + alphabet[a] + ":\t" + str(tuple(dirs[a]))

        print "..........................................."
        print 'Cantor Coding for "' + args[0] + '":'
        print tuple(code)
        print "..........................................."

    else:
        parser.print_help()

if __name__ == "__main__":
    main()

